// https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/

// 算法思路总结：
// 1. 使用动态规划维护正数乘积长度和负数乘积长度
// 2. f[i]表示以i结尾的正乘积最大长度
// 3. g[i]表示以i结尾的负乘积最大长度
// 4. 根据当前数值正负进行状态转移
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int getMaxLen(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 0) return 0;

        vector<int> f(m + 1, 0), g(m + 1, 0);
        int ret = 0;
        for (int i = 1 ; i <= m ; i++)
        {
            if (nums[i - 1] == 0) f[i] = g[i] = 0;
            else if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,-2,-3,4}, v2 = {0,1,-2,-3,-4};
    Solution sol;

    cout << sol.getMaxLen(v1) << endl;
    cout << sol.getMaxLen(v2) << endl;

    return 0;
}